


#include <iostream>
#include <string>
#include <vector>
using namespace std;

class Solution
{
public:
    string multiply1(string num1, string num2)
    {
        if ("1" == num1)
            return num2;
        if ("1" == num2)
            return num1;
        if ("0" == num1 || "0" == num2)
            return string("0");

        string res;
        int n1 = num1.size(), n2 = num2.size();
        vector<int> tmp(n1 + n2 + 1);

        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());

        for (int i = 0; i < n1; ++i)
        {
            for (int j = 0; j < n2; ++j)
            {
                tmp[i + j] += (num1[i] - '0') * (num2[j] - '0');
            }
        }

        for (int i = 0; i < n1 + n2; ++i)
        {
            if (tmp[i] > 9)
                tmp[i + 1] += tmp[i] / 10;
            tmp[i] %= 10;
            res += to_string(tmp[i]);
        }

        while ('0' == res.back())
        {
            res.pop_back();
        }
        reverse(res.begin(), res.end());

        return res;
    }

    string multiply2(string num1, string num2)
    {
        if ("1" == num1)
            return num2;
        if ("1" == num2)
            return num1;
        if ("0" == num1 || "0" == num2)
            return string("0");

        string res;
        int n1 = num1.size(), n2 = num2.size();
        vector<int> tmp(n1 + n2 + 1);

        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());

        for (int i = 0; i < n1; ++i)
        {
            for (int j = 0; j < n2; ++j)
            {
                tmp[i + j] += (num1[i] - '0') * (num2[j] - '0');

                if (i + j + 1 < n1 + n2 && tmp[i + j] > 9)
                {
                    tmp[i + j + 1] += tmp[i + j] / 10;
                    tmp[i + j] %= 10;
                }
            }
        }

        for (int i = n1 + n2; i >= 0; --i)
        {
            if (tmp[i])
            {
                while (i >= 0)
                {
                    res += to_string(tmp[i--]);
                }
            }
        }

        return res;
    }

    string decodeString1(string s)
    {
        string res;
        int n = s.size();

        for (int i = 0, j = 0; i < n; ++i)
        {
            if (']' == s[i])
            {
                string stmp;
                string scnt;
                j = res.size() - 1;

                while (j >= 0 && res[j] != '[')
                {
                    stmp += res[j];
                    --j;
                }
                reverse(stmp.begin(), stmp.end());
                --j;

                while (j >= 0 && isdigit(res[j]))
                {
                    scnt += res[j];
                    --j;
                }
                reverse(scnt.begin(), scnt.end());
                res.resize(j + 1);

                for (int k = 0, cnt = stoi(scnt); k < cnt; ++k)
                {
                    res += stmp;
                }
            }
            else
            {
                res += s[i];
            }
        }

        return res;
    }

    string decodeString2(string s)
    {
        vector<int> v;
        vector<string> vs;
        int n = s.size();

        for (int i = 0; i < n;)
        {
            if (isdigit(s[i]))
            {
                int tmp = 0;

                while (isdigit(s[i]))
                {
                    tmp = tmp * 10 + (s[i++] - '0');
                }
                v.push_back(tmp);
            }
            else
            {
                if (']' == s[i])
                {
                    string tmp;

                    for (int j = 0, cnt = v.back(); j < cnt; ++j)
                    {
                        tmp += vs.back();
                    }
                    v.pop_back();
                    vs.pop_back();

                    if (1 == vs.size())
                    {
                        vs.back() = tmp;
                    }
                    else
                    {
                        vs.pop_back();
                        vs.back() = tmp;
                    }
                }
                else if ('[' == s[i])
                {
                    vs.push_back(string(1, s[i]));
                }
                else
                {
                    if ("[" == vs.back())
                        vs.push_back(string(1, s[i]));
                    else
                        vs.back() += s[i];
                }
                ++i;
            }
        }

        return vs[0];
    }
};

void Test1()
{
    string s("3[a2[c]]");

    Solution().decodeString2(s);
}

int main()
{
    Test1();

	return 0;
}